// 
//
// Author: Christopher Schwarzer
// Date: 12/2011
//
//
#include "ShapeOrganism.h"

#include <stdlib.h>
#include <string.h>

using namespace std;

namespace Shape
{

char sideNames[SIDE_COUNT]= {'F','R','B','L'};

std::ostream& operator<<(std::ostream& os, const Tuple& t)
{
	os << t.x << "|" << t.y;
	return os;
}

////////////////////////////////////////////////////////////////////////////////
/// class Node
////////////////////////////////////////////////////////////////////////////////

ostream& operator<<(ostream& os, const Node& node)
{
    os << "node " << node.id;
    os << " (";
    for(int i = 0; i < SIDE_COUNT; i++)
    {
        if(node.connections[i] != NULL)
        {
            os << sideNames[i] << ":" << node.connections[i]->id << " ";
        }
    }
    os << ") " << node.pos << " " << node.rot << " " << node.parent;
    return os;
}

Node::Node(int id) :
	pos(), id(id), rot(0), parent(-1)
{
	memset(connections, 0, SIDE_COUNT * sizeof(Node*));
}

bool Node::IsLeaf() const
{
	int n = 0;
	for (int i = 0; i < SIDE_COUNT; i++)
	{
		if (connections[i] != NULL)
			n++;
	}
	return n <= 1;
}

// Removes this from the shape only if this is a leaf, otherwise returns false
bool Node::RemoveLeaf()
{
	if (!IsLeaf())
		return false;
	
	// Check all sides for neighbours
	for (int i = 0; i < SIDE_COUNT; i++)
	{
		if (connections[i] != NULL)
		{
			Node* neighbour = connections[i];
			// Remove this from the neighbours neighbourhood
			for (int j = 0; j < SIDE_COUNT; j++)
			{
				if (neighbour->connections[j] == this)
					neighbour->connections[j] = NULL;
			}
			connections[i] = NULL;
		}
	}
	return true;
}

Tuple Node::GetPosOfSide(side_t side) const
{
	Tuple result = pos;
	int k = (side + rot) % 4;
	switch (k)
	{
		case SIDE_FRONT: result.y++; break;
		case SIDE_RIGHT: result.x++; break;
		case SIDE_BACK: result.y--; break;
		case SIDE_LEFT: result.x--; break;
		default: cout << "Error: GetPosOfside_t " << k << endl; break;
	}
	return result;
}
 
// Adds a new node to the given side only if the side is empty, otherwise returns null
Node* Node::AddLeaf(id_t id, side_t parentside, side_t childside)
{
	if (connections[parentside] != NULL)
		return NULL;
	Node* newnode = new Node(id);
	connections[parentside] = newnode;
	newnode->connections[childside] = this;
	
	newnode->pos = GetPosOfSide(parentside);
	newnode->rot = (rot + (6 - childside + parentside)) % 4;
	newnode->parent = childside;
	return newnode;
}

// Rotates this by the given amount of sides
void Node::Rotate(int bysides)
{
	bysides %= SIDE_COUNT;
	Node* tempcons[SIDE_COUNT];
	for (int i = 0; i < SIDE_COUNT; i++)
		tempcons[i + bysides] = connections[i];
	for (int i = 0; i < SIDE_COUNT; i++)
		connections[i] = tempcons[i];
	rot = (rot + bysides) % SIDE_COUNT;
	parent = (parent + bysides) % SIDE_COUNT;
}

////////////////////////////////////////////////////////////////////////////////
/// class Organism
////////////////////////////////////////////////////////////////////////////////

ostream& operator<<(ostream& os, const Organism& og)
{
    os << "Organism with " << og.nodeList.size() << " nodes" << endl;
	for(unsigned int i=0;i<og.nodeList.size();i++)
		os << *og.nodeList[i] << endl;
		
	for (int y = og.mapSize - 1; y >= 0; y--)
	{
		for (int x = 0; x < og.mapSize; x++)
			os << *og.MapAt(x, y);
		os << endl;
	}
		
    return os;
}

Organism::Organism(int maxs) :
	maxSpread(maxs + 1), mapSize((maxs * 2) + 1), nodeIDCount(0)
{
	map = new uint8_t[mapSize * mapSize];
	memset(map, '.', mapSize * mapSize);

	AddNode((Node*)NULL, SIDE_FRONT, SIDE_FRONT);
}

Organism::Organism(const Organism& original) : 
	maxSpread(original.maxSpread), mapSize(original.mapSize), nodeIDCount(original.nodeIDCount)
{
	map = new uint8_t[mapSize * mapSize];
	memcpy(map, original.map, sizeof(uint8_t) * mapSize * mapSize);

	for (NodeList::const_iterator iter = original.nodeList.begin(); iter != original.nodeList.end(); iter++)
	{
		Node* orignode = *iter;
		Node* mynode = new Node(orignode->id);
		nodeList.push_back(mynode);
		mynode->pos = orignode->pos;
		mynode->rot = orignode->rot;
		mynode->parent = orignode->parent;
	}
	
	for (size_t i = 0; i < nodeList.size(); i++)
	{
		Node* orig = original.nodeList[i];
		Node* copy = nodeList[i];
		
		for (int s = 0; s < SIDE_COUNT; s++)
		{
			if (orig->connections[s] != NULL)
			{
				int nb = original.FindNodeIndex(orig->connections[s]);
				copy->connections[s] = nodeList[nb];
			}
		}
	}
}

Organism::~Organism()
{
	delete[] map;

	for (NodeList::iterator iter = nodeList.begin(); iter != nodeList.end(); iter++)
	{
		delete *iter;
	}
}

void Organism::PostDeserializeInit(Node* node, side_t sideFromParent)
{
	nodeList.push_back(node);
	if (node->id >= nodeIDCount)
		nodeIDCount = node->id + 1;
	if (node->parent == -1)
	{
		node->pos.x = 0;
		node->pos.y = 0;
		node->rot = 0;
		*MapPos(node->pos) = '*';
	}
	else
	{
		Node* parent = node->GetParent();
		node->pos = parent->GetPosOfSide(sideFromParent);
		node->rot = (parent->rot + (6 - node->parent + sideFromParent)) % 4;
		*MapPos(node->pos) = '+';
	}

	for (side_t i = 0; i < SIDE_COUNT; i++)
	{
		if (i != node->parent && node->connections[i] != NULL)
			PostDeserializeInit(node->connections[i], i);
	}
}

id_t Organism::AddNode(id_t parent, side_t parentSide, side_t childSide)
{
	Node* n = AddNode(GetNode(parent), parentSide, childSide);
	if (n == NULL)
		return -1;
	else
		return n->GetID();
}

Node* Organism::AddNode(Node* parent, side_t parentSide, side_t childSide)
{
	if (parent == NULL)
	{
		if (nodeList.size() > 0)
			return NULL;
		Node* root = new Node(nodeIDCount++);
		nodeList.push_back(root);
		*MapPos(root->GetPos()) = '*';
		return root;
	}

	if (parent->connections[parentSide] != NULL)
		return NULL;
	if (IsPosFree(parent->GetPosOfSide(parentSide), (parent->rot + parentSide) % 4))
	{
		Node* newNode = parent->AddLeaf(nodeIDCount++, parentSide, childSide);
		nodeList.push_back(newNode);
		*MapPos(newNode->GetPos()) = '+';
		return newNode;
	}
	else
		return NULL;
}

Node* Organism::GetNode(id_t id) const
{
	for (NodeList::const_iterator iter = nodeList.begin(); iter != nodeList.end(); iter++)
	{
		Node* node = *iter;
		if (node->id == id)
			return node;
	}
	return NULL;
}

void Organism::GetExtends(Tuple& min, Tuple& max) const
{
	for (NodeList::const_iterator iter = nodeList.begin(); iter != nodeList.end(); iter++)
	{
		Node* node = *iter;
		Tuple p = node->pos;
		if (p.x < min.x)
			min.x = p.x;
		else if (p.x > max.x)
			max.x = p.x;
		if (p.y < min.y)
			min.y = p.y;
		else if (p.y > max.y)
			max.y = p.y;
	}
}

NodeList Organism::GetLeaves() const
{
	NodeList result;
	for (NodeList::const_iterator iter = nodeList.begin(); iter != nodeList.end(); iter++)
	{
		Node* node = *iter;
		if (node->IsLeaf())
			result.push_back(node);
	}
	return result;
}

bool RandB()
{
	return rand() & 1;
}

int RandI(int max)
{
	return rand() % max;
}

bool Organism::IsPosFree(const Tuple& p, int side)
{
	int x = p.x + maxSpread;
	int y = p.y + maxSpread;

	// Check if its too close to the border
	if (x < 1 || x > mapSize -2 ||
		y < 1 || y > mapSize - 2)
		return false;

	// Check if its occupied
	if (*MapAt(x, y) <= '+')
	{
		//cout << "E";
		//*MapAt(x, y) = '!';
		return false;
	}
	//*MapAt(x, y) = '?';

	// Check if its too close to something else
	switch(side)
	{
		case SIDE_FRONT:
			if (*MapAt(x + 1, y) <= '+' ||
				*MapAt(x - 1, y) <= '+' ||
				*MapAt(x, y + 1) <= '+' ||
				*MapAt(x + 1, y + 1) <= '+' ||
				*MapAt(x - 1, y + 1) <= '+'
				)
				return false;
			break;
		case SIDE_RIGHT:
			if (*MapAt(x, y + 1) <= '+' ||
				*MapAt(x, y - 1) <= '+' ||
				*MapAt(x + 1, y) <= '+' ||
				*MapAt(x + 1, y + 1) <= '+' ||
				*MapAt(x + 1, y - 1) <= '+' )
				return false;
			break;
		case SIDE_BACK:
			if (*MapAt(x + 1, y) <= '+' ||
				*MapAt(x - 1, y) <= '+' ||
				*MapAt(x, y - 1) <= '+' ||
				*MapAt(x + 1, y - 1) <= '+' ||
				*MapAt(x - 1, y - 1) <= '+')
				return false;
			break;
		case SIDE_LEFT:
			if (*MapAt(x, y + 1) <= '+' ||
				*MapAt(x, y - 1) <= '+' ||
				*MapAt(x - 1, y) <= '+' ||
				*MapAt(x - 1, y + 1) <= '+' ||
				*MapAt(x - 1, y - 1) <= '+')
				return false;
			break;
	}
	//*MapAt(x, y) = 'Y';
	return true;
}

struct Candidate { Node* node; side_t side; };
void Organism::Mutate(int mutationCount)
{
	for (int i = 0; i < mutationCount; i++)
	{
		if (RandB() == 0)
			RemoveRandom();
		else
			AddRandom();
	}
}
    
void Organism::MutateFixed()
{
    AddNode(GetRoot(), SIDE_LEFT, SIDE_BACK);
}

Organism* Organism::CreateMutant(int mutationCount) const
{
	Organism* org = new Organism(*this);
	org->Mutate(mutationCount);
	return org;
}

void Organism::AddRandom()
{
	// for each NODE
	// 	for all free SIDEs of NODE
	//    make collision check, regarding direction
	//    if ok -> store NODE and SIDE into LIST end if
	//   end for
	// end for
	// pick ONE from LIST
	// create ONE
	vector<Candidate> candidates;
	for (NodeList::iterator iter = nodeList.begin(); iter != nodeList.end(); iter++)
	{
		Node* node = *iter;
		for (side_t s = 0; s < SIDE_COUNT; s++)
			if (node->connections[s] == NULL)
			{
				// collision check
				Tuple sidepos = node->GetPosOfSide(s);
				if (IsPosFree(sidepos, (node->rot + s)%4))
				{
					Candidate c = {node, s};
					candidates.push_back(c);
				}
			}
	}

	//cout << "Mutate add - found pos " << candidates.size() << endl;
	if (candidates.size() > 0)
	{
		int p = RandI((int)candidates.size());
		Candidate& c = candidates[p];
		//cout << "Mutate: Add leaf at " << c.node->GetPosOfSide(c.side) << endl;
		side_t childside = RandI(SIDE_COUNT);
		if (AddNode(c.node, c.side, childside) == NULL)
			cerr << "ERROR: AddRandom failed to add node " << c.node->GetPosOfSide(c.side) << endl;
	}
}

void Organism::RemoveRandom()
{
	NodeList leaves = GetLeaves();
	//cout << "Mutate remove - found leaves " << leaves.size() << endl;
	int p = RandI((int)leaves.size());
	Node* pick = leaves[p];
	if (pick->pos.x == 0 && pick->pos.y == 0)
	{
		//cout << "Mutate: Wont remove parent node" << endl;
		return;
	}
		
	//cout << "Mutate: Remove leaf " << *pick << endl;
	if (nodeList.size() == 1)
		return;
	pick->RemoveLeaf();
	*MapPos(pick->GetPos()) = '.';
	nodeList.erase(nodeList.begin() + FindNodeIndex(pick));
	delete pick;
}

void Organism::RotateRandom()
{
	cerr << "Warning - Organism::RotateRandom: not implemented yet" << endl;
}

Organism* Organism::CreateRecombinant(const Organism& mate) const
{
	cerr << "Warning - Organism::CreateRecombinant: using trivial implementation" << endl;
	if (RandB())
		return new Organism(*this);
	else
		return new Organism(mate);
}

bool Organism::Match(const Organism* other) const
{
	if (other == NULL)
		return false;
	if (other  == this)
		return true;
	if (other->maxSpread != maxSpread)
		return false;
	if (other->nodeList.size() != nodeList.size())
		return false;
	for (int i = 0; i < mapSize * mapSize; i++)
			if ( (map[i] <= '+') != (other->map[i] <= '+'))
				return false;
	
	return true;
}

int Organism::FindNodeIndex(Node* node) const
{
	for (size_t i = 0; i < nodeList.size(); i++)
	{
		if (nodeList[i] == node)
			return (int) i;
	}
	return -1;
}

}
